Graph: A set of nodes (a.k.a. vertices) connected pairwise by edges:
Path: A sequence of vertices connected by edges
Cycle: A path whose first and last vertices are the same:
Two vertices are connected if there is a path between them:
Common convention: Number nodes irrespective of label
Map<Label, Integer> to lookup a vertex by labelGraph API
public class Graph { /** Creates empty graph with `V` vertices */ public Graph(int V); /** Adds an edge `v`-`w` */ public void addEdge(int v, int w); /** Vertices adjacent to `v` */ Iterable<Integer> adj(int v); /** Returns the number of vertices */ int V(); /** Returns the number of edges */ int E(); }
Example client
/** Returns the degree of vertex `v` in graph `G` */ public static int degree(Graph G, int v) { int degree = 0; for (int w : G.adf()) { degree += 1; } return degree; }
| v\w | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 0 | 0 | 1 | 0 |
Collection of all edges:
HashSet<Edge> where each Edge is a pair of ints{(0, 1), (0, 2), (1, 2)}Common approach: Maintain array of lists indexed by vertex number:
| Graph | Representation | |
|---|---|---|
Printing an entire graph
for (int v = 0; v < G.V(); v += 1) { for (int w : G.adj(v)) { System.out.println(v + "-" + w); } }
for (int w): for (int v): How to interpret :
| Representation | addEdge(s, t) |
for(w : adf(v)) |
printGraph() |
hasEdge(s, t) |
Space used |
|---|---|---|---|---|---|
| Adjacency matrix | |||||
| Edge Set | |||||
| Adjacency list | to |
(Note: printGraph() and hasEdge(s, t) are not part of the Graph class's API)
In practice, adjacency list is most common:
adj(v)Suppose we want to know if there exists a path from vertex s = 0 to vertex t = 7:
s == t, if so, return trues's neighbors for connectivity to t=> Fail into infinite loop...
ss == t, if so, return trues's unmarked neighbors for connectivity to `t=> This idea of exploring the entire subgraph for each neighbor is known as Depth First Search traversal.
Common design pattern in graph algorithms: Decouple type from processing algorithm:
Graph objectRecursive Implementation: demo
public class DepthFirstPaths { private boolean[] marked; // Tracks marked vertices private int[] edgeTo; // Tracks from which vertex the path came to an edge private int s; /** Finds all paths from `G`'s vertex `s` */ public DepthFirstPaths(Graph G, int s) { ... // Data structure initialization dfs(G, s); } private void dfs(Graph G, int v) { marked[v] = true; for (int w : G.adj(v)) { if (!markded[w]) { edgeTo[w] = v; dfs(G, w); } } } /** Checks there is a path from `s` to `t` */ public boolean hasPathTo(int t) { return marked[t]; } /** Returns path from `s` to `v` (if any) */ public Iterable<Integer> pathTo(int t) { ... } }
Suppose we have tasks 0 through 7, where an arrow from v to w indicates that v must happen before w:
[0, 2, 1, 3, 5, 4, 7, 6], [2, 0, 3, 5, 1, 4, 6, 7]Perform DFS traversals from every vertex (with indegree 0), NOT clearing markings in between traversals:
[7, 4, 1, 3, 0, 6, 5, 2][2, 5, 6, 0, 3, 1, 4, 7]
Can think of this procedure as sorting our nodes so that they appear in an order consistent with edge:
public class DepthFirstPaths { private boolean[] marked; private Stack<Integer> reversePostorder; // Use a stack instead of a list public DepthFirstPaths(Graph G) { reversePostorder = new Stack<>(); marked = new boolean[G.V()]; for (int v = 0; v < G.V(); v += 1) { if (!marked[v]) { dfs(G, v); } // Perform DFS from all unmarked vertices } } private void dfs(Graph G, int v) { marked[v] = true; for (int w : G.adj(v)) { if (!marked[w]) { dfs(G, w); } } reversePostorder.push(v); // 'Visit' vertex by pushing it in a stack } public Iterable<Integer> reversePostorder() { return reversePostorder; } }
Given the graph below, find the shortest path from 0 to every other vertex:
Level-order provides the shortest paths from 0 to every reachable vertex from 0 by definition !: "Level order" is referred as "the order visited by Breadth First Search"
s and mark that vertex
v from queuev and mark thempublic class BreadthFirstPaths { private boolean[] marked; private int[] edgeTo; ... private void bfs(Graph G, int s) { Queue<Integer> fringe = new Queue<>(); fringe.enqueue(s); marked[s] = true; while(!fringe.isEmpty()) { int v = fringe.dequeue(); for (int w : G.adj(v)) { fringe.enqueue(w); marked[w] = true; edgeTo[w] = v; } } } }
| Problem | Description | Efficiency |
|---|---|---|
| s-t paths | Find a path from s to every reachable vertex |
time space |
| Topological sort | Find an ordering of vertices consistent with directed edges | |
| s-t shortest path | Find a shortest path from s to every reachable vertex |
Graph can have no edges touching source